package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * 1838. 最高频元素的频数
 *
 * @author liw
 * @version 1.0
 * @date 2021/7/19 10:04
 */
public class MaxFrequency {

    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int length = nums.length;
        int st = 0;
        int item = 0;
        int max = 1;
        for (int i = 1; i < length; i++) {
            int value = nums[i];
            item += (i - st) * (value - nums[i - 1]);
            while (item > k) {
                item -= (value - nums[st]);
                st++;
            }
            max = Math.max(max, (i - st + 1));

        }
        return max;
    }


    public int maxFrequency1(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long total = 0;
        int l = 0, res = 1;
        for (int r = 1; r < n; ++r) {
            total += (long) (nums[r] - nums[r - 1]) * (r - l);
            while (total > k) {
                total -= nums[r] - nums[l];
                ++l;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }

}
